package com.linyaonan.labuladong._01_list._02;

import java.time.temporal.Temporal;

/**
 * 给一个链表的头节点head和一个特定值x，对链表进行分割，使得所有小于x的节点都出现在大于等于x节点之前
 *
 * @author: Lin
 * @date: 2022/7/25
 */
public class SplitList {

    public ListNode splitList(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode s1 = new ListNode(-1);
        ListNode s2 = s1;
        ListNode b1 = new ListNode(-1);
        ListNode b2 = b1;

        while (head != null) {
            if (head.val < x) {
                s1.next = head;
                s1 = s1.next;
            } else {
                b1.next = head;
                b1 = b1.next;
            }
            // 需要断开原链表的next指针，否则会出现环形链表
            ListNode tmp = head.next;
            head.next = null;
            head = tmp;
        }

        s1.next = b2.next;
        return s2.next;

    }

}
